package leetCode.fourthWeek;

public class Code_79 {
  public boolean exist(char[][] board, String word) {
    for (int i = 0; i < board.length; i++) {
      for (int j = 0; j < board[0].length; j++) {
        if (dfs(board, word, i, j, 0)) {
          return true;
        }
      }
    }
    return false;
  }

  /**
   * @param board 原有的字符数组
   * @param word 需要匹配的字符串
   * @param i 当前的行, 初始时传入起始点的坐标
   * @param j 当前的列, 初始时传入起始点的坐标
   * @param k 当前匹配到的字符串的长度
   */
  public boolean dfs(char[][] board, String word, int i, int j, int k) {
    if (k >= word.length()) {
      return true;
    }
    if (false
        || i >= board.length
        || i < 0
        || j >= board[0].length
        || j < 0
        || board[i][j] != word.charAt(k)) {
      return false;
    }
    board[i][j] += 256;
    Boolean res =
        false
            || dfs(board, word, i, j + 1, k + 1)
            || dfs(board, word, i, j - 1, k + 1)
            || dfs(board, word, i - 1, j, k + 1)
            || dfs(board, word, i + 1, j, k + 1);
    board[i][j] -= 256;
    return res;
  }
}
